/*-------------------------------------------------------------------------
 *
 * pg_inherits.c
 *	  支持pg_inherits关系操作的常规例程
 *
 * 注意：目前，该模块主要包含查询函数；pg_inherits条目的实际创建和删除主要在tablecmds.c中完成。
 * 也许有一天那段代码应该移到这里，但它必须与pg_depend更新等其他内容解耦。
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  src/backend/catalog/pg_inherits.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "access/genam.h"
#include "access/htup_details.h"
#include "access/table.h"
#include "catalog/indexing.h"
#include "catalog/pg_inherits.h"
#include "parser/parse_type.h"
#include "storage/lmgr.h"
#include "utils/builtins.h"
#include "utils/fmgroids.h"
#include "utils/memutils.h"
#include "utils/snapmgr.h"
#include "utils/syscache.h"

/*
 * find_all_inheritors 中使用的哈希表项。见下文。
 */
typedef struct SeenRelsEntry
{
	Oid			rel_id;			/* 关系oid */
	int			list_index;		/* 在输出列表中的位置 */
} SeenRelsEntry;

/*
 * find_inheritance_children
 *
 * 返回一个包含所有直接从OID为'parentrelId'的关系继承的关系OID的列表。
 *
 * 在每个子关系上会获取指定的锁类型（但不会在给定的关系上获取；调用者应该已经对其加锁）。如果锁模式是NoLock，则不获取任何锁，但调用者必须注意可能的竞争条件，以防子关系被删除。
 *
 * 被标记为分离的分区将被省略；有关详细信息，请参见find_inheritance_children_extended。
 */
List * find_inheritance_children(Oid fc_parentrelId, LOCKMODE fc_lockmode)
{
	return find_inheritance_children_extended(fc_parentrelId, true, fc_lockmode,
											  NULL, NULL);
}

/*
 * find_inheritance_children_extended
 *
 * 和find_inheritance_children一样，但具有关于分离分区的更多选项。
 *
 * 如果分区的pg_inherits行被标记为“分离待定”，
 * *detached_exist（如果不为null）被设置为true。
 *
 * 如果omit_detached为true，并且存在一个活动快照（与用于扫描pg_inherits的目录快照不同！），并且该快照可以看到标记为“分离待定”的pg_inherits元组，则该分区将从输出列表中省略。这使得分区的可见性取决于标记这些分区为分离的事务是否在活动快照中被视为已提交。此外，*detached_xmin（如果不为null）被设置为分离分区行的xmin值。
 */
List * find_inheritance_children_extended(Oid fc_parentrelId, bool fc_omit_detached,
								   LOCKMODE fc_lockmode, bool *fc_detached_exist,
								   TransactionId *fc_detached_xmin)
{
	List	   *fc_list = NIL;
	Relation	fc_relation;
	SysScanDesc fc_scan;
	ScanKeyData fc_key[1];
	HeapTuple	fc_inheritsTuple;
	Oid			fc_inhrelid;
	Oid		   *fc_oidarr;
	int			fc_maxoids,
				fc_numoids,
				fc_i;

	/*
	 * 如果pg_class显示该关系从未拥有一个子类，则可以跳过扫描。
	 */
	if (!has_subclass(fc_parentrelId))
		return NIL;

	/*
	 * 扫描pg_inherits并构建一个子类OID的工作数组。
	 */
	fc_maxoids = 32;
	fc_oidarr = (Oid *) palloc(fc_maxoids * sizeof(Oid));
	fc_numoids = 0;

	fc_relation = table_open(InheritsRelationId, AccessShareLock);

	ScanKeyInit(&fc_key[0],
				Anum_pg_inherits_inhparent,
				BTEqualStrategyNumber, F_OIDEQ,
				ObjectIdGetDatum(fc_parentrelId));

	fc_scan = systable_beginscan(fc_relation, InheritsParentIndexId, true,
							  NULL, 1, fc_key);

	while ((fc_inheritsTuple = systable_getnext(fc_scan)) != NULL)
	{
		/*
		 * 处理并发被分离的分区。当我们看到一个标记为“分离待定”的分区时，如果调用者请求，我们将在返回的可见分区集合中省略它，并且元组的xmin在活动快照中不再进行中。（如果没有设置活动快照，那意味着我们没有运行用户查询，因此在这种情况下始终包含分离分区是可以的；如果xmin仍在活动快照中进行，那么分区尚未被分离，因此我们将其包括在内。）
		 *
		 * 进行此修改的原因是我们希望避免在REPEATABLE READ或SERIALIZABLE事务期间在RI查询中将分区视为存在：这种查询使用与普通（用户）查询不同的快照。
		 */
		if (((Form_pg_inherits) GETSTRUCT(fc_inheritsTuple))->inhdetachpending)
		{
			if (fc_detached_exist)
				*fc_detached_exist = true;

			if (fc_omit_detached && ActiveSnapshotSet())
			{
				TransactionId fc_xmin;
				Snapshot	fc_snap;

				fc_xmin = HeapTupleHeaderGetXmin(fc_inheritsTuple->t_data);
				fc_snap = GetActiveSnapshot();

				if (!XidInMVCCSnapshot(fc_xmin, fc_snap))
				{
					if (fc_detached_xmin)
					{
						/*
						 * 不应发生两个分离的分区（请参见MarkInheritDetached中的检查），但如果发生了，则跟踪两个中的较新者。确保警告用户，以便他们可以进行清理。由于这只是对可能损坏的目录的交叉检查，因此我们不会把它作为一个完整的错误消息。
						 */
						if (*fc_detached_xmin != InvalidTransactionId)
						{
							elog(WARNING, "more than one partition pending detach found for table with OID %u",
								 fc_parentrelId);
							if (TransactionIdFollows(fc_xmin, *fc_detached_xmin))
								*fc_detached_xmin = fc_xmin;
						}
						else
							*fc_detached_xmin = fc_xmin;
					}

					/* 不要将分区添加到输出列表中 */
					continue;
				}
			}
		}

		fc_inhrelid = ((Form_pg_inherits) GETSTRUCT(fc_inheritsTuple))->inhrelid;
		if (fc_numoids >= fc_maxoids)
		{
			fc_maxoids *= 2;
			fc_oidarr = (Oid *) repalloc(fc_oidarr, fc_maxoids * sizeof(Oid));
		}
		fc_oidarr[fc_numoids++] = fc_inhrelid;
	}

	systable_endscan(fc_scan);

	table_close(fc_relation, AccessShareLock);

	/*
	 * 如果我们找到了超过一个子项，则按OID对它们进行排序。这确保了无论索引扫描的变化如何，行为都是相对一致的。这一点很重要，因为我们需要确保所有后端以相同的顺序锁定子项，以避免不必要的死锁。
	 */
	if (fc_numoids > 1)
		qsort(fc_oidarr, fc_numoids, sizeof(Oid), oid_cmp);

	/*
	 * 获取锁并构建结果列表。
	 */
	for (fc_i = 0; fc_i < fc_numoids; fc_i++)
	{
		fc_inhrelid = fc_oidarr[fc_i];

		if (fc_lockmode != NoLock)
		{
			/* 获取锁以同步并发删除 */
			LockRelationOid(fc_inhrelid, fc_lockmode);

			/*
			 * 现在我们已经获得锁，仔细检查一下关系是否真的存在。如果不存在，则假设它在我们等待获取锁时被删除，并忽略它。
			 */
			if (!SearchSysCacheExists1(RELOID, ObjectIdGetDatum(fc_inhrelid)))
			{
				/* 释放无用的锁 */
				UnlockRelationOid(fc_inhrelid, fc_lockmode);
				/* 并忽略此关系 */
				continue;
			}
		}

		fc_list = lappend_oid(fc_list, fc_inhrelid);
	}

	pfree(fc_oidarr);

	return fc_list;
}


/*
 * find_all_inheritors -
 *		返回一个关系OID的列表，包括给定关系以及所有直接或间接继承该关系的关系。
 *		可选地，它还返回在给定关系的继承树中找到的每个关系的父关系数量。
 *
 * 在所有子关系上获取指定的锁类型（但不会在给定的关系上获取；调用者应该已经对其加锁）。如果锁模式是NoLock，则不获取任何锁，但调用者必须注意可能的竞争条件，以防子关系被删除。
 *
 * 注意 - 当前没有该例程的调用者对子关系并发分离感兴趣，因此没有包含它们的规定。
 */
List * find_all_inheritors(Oid fc_parentrelId, LOCKMODE fc_lockmode, List **fc_numparents)
{
	/* hash表用于O(1) rel_oid -> rel_numparents单元查找 */
	HTAB	   *fc_seen_rels;
	HASHCTL		fc_ctl;
	List	   *fc_rels_list,
			   *fc_rel_numparents;
	ListCell   *fc_l;

	fc_ctl.keysize = sizeof(Oid);
	fc_ctl.entrysize = sizeof(SeenRelsEntry);
	fc_ctl.hcxt = CurrentMemoryContext;

	fc_seen_rels = hash_create("find_all_inheritors temporary table",
							32, /* 从小开始并扩展 */
							&fc_ctl,
							HASH_ELEM | HASH_BLOBS | HASH_CONTEXT);

	
/*
	 * 我们从给定的 rel 开始构建一个列表，并添加所有直接和
	 * 间接的子项。我们可以使用一个列表作为已经找到的 rel 的记录
	 * 和尚未扫描以获取更多子项的 rel 的议程。这有点棘手，但有效，
	 * 因为 foreach() 宏在循环底部才会获取下一个列表元素。
	 * 注意，我们不能在输出列表中保留指针；但索引是
	 * 足够的。
	 */
	fc_rels_list = list_make1_oid(fc_parentrelId);
	fc_rel_numparents = list_make1_int(0);

	foreach(fc_l, fc_rels_list)
	{
		Oid			fc_currentrel = lfirst_oid(fc_l);
		List	   *fc_currentchildren;
		ListCell   *fc_lc;

		/* 获取该 rel 的直接子项 */
		fc_currentchildren = find_inheritance_children(fc_currentrel, fc_lockmode);

		/*
		 * 只将未被查看的子项添加到队列。这避免了由于
		 * 从同一个父项的多个继承路径而导致的重复条目。
		 * （这也会让我们避免进入无限循环，尽管理论上
		 * 继承图中不可能有循环。）
		 */
		foreach(fc_lc, fc_currentchildren)
		{
			Oid			fc_child_oid = lfirst_oid(fc_lc);
			bool		fc_found;
			SeenRelsEntry *fc_hash_entry;

			fc_hash_entry = hash_search(fc_seen_rels, &fc_child_oid, HASH_ENTER, &fc_found);
			if (fc_found)
			{
				/* 如果 rel 已经在其中，则增加父项计数器 */
				ListCell   *fc_numparents_cell;

				fc_numparents_cell = list_nth_cell(fc_rel_numparents,
												fc_hash_entry->list_index);
				lfirst_int(fc_numparents_cell)++;
			}
			else
			{
				/* 如果不在其中，则添加它。最初期望有 1 个父项。 */
				fc_hash_entry->list_index = list_length(fc_rels_list);
				fc_rels_list = lappend_oid(fc_rels_list, fc_child_oid);
				fc_rel_numparents = lappend_int(fc_rel_numparents, 1);
			}
		}
	}

	if (fc_numparents)
		*fc_numparents = fc_rel_numparents;
	else
		list_free(fc_rel_numparents);

	hash_destroy(fc_seen_rels);

	return fc_rels_list;
}


/*
 * has_subclass - 这个关系是否有子类？
 *
 * 在当前实现中，has_subclass 返回一个特定类是否
 * *可能* 有一个子类。如果一个类有一个稍后被删除的子类，
 * 它将不会返回正确的结果。这是因为 pg_class 中的
 * relhassubclass 在子类被删除时不会立即更新，
 * 主要是因为并发性问题。
 *
 * 目前，has_subclass 仅作为跳过不必要的继承搜索的效率技巧，
 * 所以这是可以的。注意，对没有子类的表进行 ANALYZE
 * 将清理过时的 relhassubclass 标志。
 *
 * 尽管这实际上并未触及 pg_inherits，但在这里保留
 * 是合理的，因为它通常与这里的其他例程一起使用。
 */
bool has_subclass(Oid fc_relationId)
{
	HeapTuple	fc_tuple;
	bool		fc_result;

	fc_tuple = SearchSysCache1(RELOID, ObjectIdGetDatum(fc_relationId));
	if (!HeapTupleIsValid(fc_tuple))
		elog(ERROR, "cache lookup failed for relation %u", fc_relationId);

	fc_result = ((Form_pg_class) GETSTRUCT(fc_tuple))->relhassubclass;
	ReleaseSysCache(fc_tuple);
	return fc_result;
}

/*
 * has_superclass - 这个关系是否从另一个继承？
 *
 * 与 has_subclass 不同，可以依赖它给出准确的答案。
 * 然而，调用者必须持有给定关系的锁，以便它不会
 * 同时被添加到或从继承层次中移除。
 */
bool has_superclass(Oid fc_relationId)
{
	Relation	fc_catalog;
	SysScanDesc fc_scan;
	ScanKeyData fc_skey;
	bool		fc_result;

	fc_catalog = table_open(InheritsRelationId, AccessShareLock);
	ScanKeyInit(&fc_skey, Anum_pg_inherits_inhrelid, BTEqualStrategyNumber,
				F_OIDEQ, ObjectIdGetDatum(fc_relationId));
	fc_scan = systable_beginscan(fc_catalog, InheritsRelidSeqnoIndexId, true,
							  NULL, 1, &fc_skey);
	fc_result = HeapTupleIsValid(systable_getnext(fc_scan));
	systable_endscan(fc_scan);
	table_close(fc_catalog, AccessShareLock);

	return fc_result;
}

/*
 * 给定两个类型 OID，确定第一个是否是继承自第二个的
 * 复杂类型（类类型）。
 *
 * 这基本上问的是第一个类型是否能够被强制转换为
 * 第二个类型。因此，我们允许第一个类型是一个在
 * 第二个类型上继承的复杂类型的域；这不会造成任何问题。
 * 但第二种类型不能是一个域。
 */
bool typeInheritsFrom(Oid fc_subclassTypeId, Oid fc_superclassTypeId)
{
	bool		fc_result = false;
	Oid			fc_subclassRelid;
	Oid			fc_superclassRelid;
	Relation	fc_inhrel;
	List	   *fc_visited,
			   *fc_queue;
	ListCell   *fc_queue_item;

	/* 我们需要处理相关的关系 OID */
	fc_subclassRelid = typeOrDomainTypeRelid(fc_subclassTypeId);
	if (fc_subclassRelid == InvalidOid)
		return false;			/* 不是复杂类型或其上的域 */
	fc_superclassRelid = typeidTypeRelid(fc_superclassTypeId);
	if (fc_superclassRelid == InvalidOid)
		return false;			/* 不是复杂类型 */

	/* 如果超类没有子类，则没有意义去搜索 */
	if (!has_subclass(fc_superclassRelid))
		return false;

	/*
	 * 从关系本身开始搜索，因此将其 relid 添加到队列中。
	 */
	fc_queue = list_make1_oid(fc_subclassRelid);
	fc_visited = NIL;

	fc_inhrel = table_open(InheritsRelationId, AccessShareLock);

	/*
	 * 使用队列对从提供的 relid 开始到根的继承图进行广度优先遍历。
	 * 注意，我们在循环内部向队列添加元素 --- 这没关系，因为 foreach() 宏在下一个循环迭代开始之前不会推进 queue_item。
	 */
	foreach(fc_queue_item, fc_queue)
	{
		Oid			fc_this_relid = lfirst_oid(fc_queue_item);
		ScanKeyData fc_skey;
		SysScanDesc fc_inhscan;
		HeapTuple	fc_inhtup;

		/*
		 * 如果我们已经见过这个 relid，则跳过它。这样可以避免在多重继承场景中做额外的工作，
		 * 也能保护我们免受 pg_inherits 中循环导致的无限循环（尽管理论上不应该发生）。
		 */
		if (list_member_oid(fc_visited, fc_this_relid))
			continue;

		/*
		 * 好的，这是一个尚未见过的 relid。将其添加到已访问 OID 的列表中，
		 * 然后找到这个 relid 继承的所有类型并将它们添加到队列中。
		 */
		fc_visited = lappend_oid(fc_visited, fc_this_relid);

		ScanKeyInit(&fc_skey,
					Anum_pg_inherits_inhrelid,
					BTEqualStrategyNumber, F_OIDEQ,
					ObjectIdGetDatum(fc_this_relid));

		fc_inhscan = systable_beginscan(fc_inhrel, InheritsRelidSeqnoIndexId, true,
									 NULL, 1, &fc_skey);

		while ((fc_inhtup = systable_getnext(fc_inhscan)) != NULL)
		{
			Form_pg_inherits fc_inh = (Form_pg_inherits) GETSTRUCT(fc_inhtup);
			Oid			fc_inhparent = fc_inh->inhparent;

			/* 如果这是目标超类，我们完成了 */
			if (fc_inhparent == fc_superclassRelid)
			{
				fc_result = true;
				break;
			}

			/* 否则添加到队列中 */
			fc_queue = lappend_oid(fc_queue, fc_inhparent);
		}

		systable_endscan(fc_inhscan);

		if (fc_result)
			break;
	}

	/* 清理 ... */
	table_close(fc_inhrel, AccessShareLock);

	list_free(fc_visited);
	list_free(fc_queue);

	return fc_result;
}

/*
 * 使用给定数据创建一个单独的 pg_inherits 行
 */
void StoreSingleInheritance(Oid fc_relationId, Oid fc_parentOid, int32 fc_seqNumber)
{
	Datum		fc_values[Natts_pg_inherits];
	bool		fc_nulls[Natts_pg_inherits];
	HeapTuple	fc_tuple;
	Relation	fc_inhRelation;

	fc_inhRelation = table_open(InheritsRelationId, RowExclusiveLock);

	/*
	 * 创建 pg_inherits 条目
	 */
	fc_values[Anum_pg_inherits_inhrelid - 1] = ObjectIdGetDatum(fc_relationId);
	fc_values[Anum_pg_inherits_inhparent - 1] = ObjectIdGetDatum(fc_parentOid);
	fc_values[Anum_pg_inherits_inhseqno - 1] = Int32GetDatum(fc_seqNumber);
	fc_values[Anum_pg_inherits_inhdetachpending - 1] = BoolGetDatum(false);

	memset(fc_nulls, 0, sizeof(fc_nulls));

	fc_tuple = heap_form_tuple(RelationGetDescr(fc_inhRelation), fc_values, fc_nulls);

	CatalogTupleInsert(fc_inhRelation, fc_tuple);

	heap_freetuple(fc_tuple);

	table_close(fc_inhRelation, RowExclusiveLock);
}

/*
 * DeleteInheritsTuple
 *
 * 删除与给定 inhrelid 匹配的 pg_inherits 元组。inhparent 可以给定为 InvalidOid，
 * 在这种情况下，将删除所有匹配 inhrelid 的元组；
 * 否则，只删除具有指定 inhparent 的元组。
 *
 * expect_detach_pending 是 inhdetachpending 标志的预期状态。
 * 如果目录行与该状态不匹配，则会引发错误。
 *
 * childname 是分区名称，如果是表；对于常规继承或处理其他关系类型时传递 NULL。
 *
 * 返回是否至少删除了一行。
 */
bool DeleteInheritsTuple(Oid fc_inhrelid, Oid fc_inhparent, bool fc_expect_detach_pending,
					const char *fc_childname)
{
	bool		fc_found = false;
	Relation	fc_catalogRelation;
	ScanKeyData fc_key;
	SysScanDesc fc_scan;
	HeapTuple	fc_inheritsTuple;

	/*
	 * 按 inhrelid 查找 pg_inherits 条目。
	 */
	fc_catalogRelation = table_open(InheritsRelationId, RowExclusiveLock);
	ScanKeyInit(&fc_key,
				Anum_pg_inherits_inhrelid,
				BTEqualStrategyNumber, F_OIDEQ,
				ObjectIdGetDatum(fc_inhrelid));
	fc_scan = systable_beginscan(fc_catalogRelation, InheritsRelidSeqnoIndexId,
							  true, NULL, 1, &fc_key);

	while (HeapTupleIsValid(fc_inheritsTuple = systable_getnext(fc_scan)))
	{
		Oid			fc_parent;

		/* 如果给定了 inhparent，则比较它，并执行实际删除。 */
		fc_parent = ((Form_pg_inherits) GETSTRUCT(fc_inheritsTuple))->inhparent;
		if (!OidIsValid(fc_inhparent) || fc_parent == fc_inhparent)
		{
			bool		fc_detach_pending;

			fc_detach_pending =
				((Form_pg_inherits) GETSTRUCT(fc_inheritsTuple))->inhdetachpending;

			/*
			 * 根据状态引发错误。这只应发生在分区上，但我们没有办法交叉验证。
			 */
			if (fc_detach_pending && !fc_expect_detach_pending)
				ereport(ERROR,
						(errcode(ERRCODE_OBJECT_NOT_IN_PREREQUISITE_STATE),
						 errmsg("cannot detach partition \"%s\"",
								fc_childname ? fc_childname : "unknown relation"),
						 errdetail("The partition is being detached concurrently or has an unfinished detach."),
						 errhint("Use ALTER TABLE ... DETACH PARTITION ... FINALIZE to complete the pending detach operation.")));
			if (!fc_detach_pending && fc_expect_detach_pending)
				ereport(ERROR,
						(errcode(ERRCODE_OBJECT_NOT_IN_PREREQUISITE_STATE),
						 errmsg("cannot complete detaching partition \"%s\"",
								fc_childname ? fc_childname : "unknown relation"),
						 errdetail("There's no pending concurrent detach.")));

			CatalogTupleDelete(fc_catalogRelation, &fc_inheritsTuple->t_self);
			fc_found = true;
		}
	}

	/* 完成 */
	systable_endscan(fc_scan);
	table_close(fc_catalogRelation, RowExclusiveLock);

	return fc_found;
}

/*
 * 返回分区的 pg_inherits 元组是否设置了 "detach pending" 标志。
 */
bool PartitionHasPendingDetach(Oid fc_partoid)
{
	Relation	fc_catalogRelation;
	ScanKeyData fc_key;
	SysScanDesc fc_scan;
	HeapTuple	fc_inheritsTuple;

	/* 我们没有好的方法来验证它确实是一个分区 */

	/*
	 * 按 inhrelid 查找 pg_inherits 条目。（应该只有一项。）
	 */
	fc_catalogRelation = table_open(InheritsRelationId, RowExclusiveLock);
	ScanKeyInit(&fc_key,
				Anum_pg_inherits_inhrelid,
				BTEqualStrategyNumber, F_OIDEQ,
				ObjectIdGetDatum(fc_partoid));
	fc_scan = systable_beginscan(fc_catalogRelation, InheritsRelidSeqnoIndexId,
							  true, NULL, 1, &fc_key);

	while (HeapTupleIsValid(fc_inheritsTuple = systable_getnext(fc_scan)))
	{
		bool		fc_detached;

		fc_detached =
			((Form_pg_inherits) GETSTRUCT(fc_inheritsTuple))->inhdetachpending;

		/* 完成 */
		systable_endscan(fc_scan);
		table_close(fc_catalogRelation, RowExclusiveLock);

		return fc_detached;
	}

	elog(ERROR, "relation %u is not a partition", fc_partoid);
	return false;				/* 保持编译器安静 */
}
